package com.LC._53;

class Solution {
//    public int maxSubArray(int[] nums) {
//        int sum = 0;
//        //
//        for(int i=0;i<nums.length;i++){
//            int temp=0;
//            for(int j=i;j<nums.length;j++){
//                sum = nums[j]+sum;
//                sum = Math.max(temp,sum);
//                temp = sum;
//            }
//        }
//        //
//
//        //状态转移方程
//        return sum;
//    }
public int maxSubArray(int[] nums) {
    int n = nums.length;
    int[] dp = new int[n];
    dp[0]=nums[0];
    for(int i=1;i<nums.length;i++){
        if(dp[i-1]>0){
            dp[i] = dp[i-1]+nums[i];
        }else{
            dp[i] = dp[i-1];//
        }
    }
    //
    int res = dp[0];
    for(int i=0;i<n;i++){
        res =Math.max(res , dp[i]);
    }
    return res;
}
    public static void main(String[] args) {
        Solution solution = new Solution();
        int[] nums = new int[]{-2,1,-3,4,-1,2,1,-5,4};
        System.out.println(solution.maxSubArray(nums));
    }
}